"""
信源编码
"""
from functools import cmp_to_key
import math

class SourceEncoding():
    def __init__(self, InputList):
        self.NewList(InputList)
    def NewList(self,InputList):
        self.InputList = InputList
        self.InputList.sort(reverse=True)
        self.H()
        self.createFanoEncodingList()
        self.createHuffmanEncodingList()
        self.createShannonlist()


    # Efficiency And code length
    def CodeLength(self,CodedList):
        codeLength=0
        for i in range(0,len(self.InputList)):
            codeLength+=len(CodedList[str(self.InputList[i])])*self.InputList[i]
        return codeLength
    def H(self):
        self.h=0
        for i in range(0,len(self.InputList)):
            self.h+=self.InputList[i]*(math.log(1/self.InputList[i])/math.log(2))
    def Efficiency(self,CodedList):
        length=self.CodeLength(CodedList)
        efficiency=self.h/length
        return efficiency
    def printEncodedList(self,EncodedList):
        for key in EncodedList.keys():
            print(key,":",EncodedList[key])


    # Fano Encoding start
    def createFanoEncodingList(self):
        self.FanoList = ["" for i in range(0, len(self.InputList))]
        self.FanoEncoding(0, len(self.InputList), self.InputList, self.FanoList)
        self.afterEncodingFanoList={}
        for i in range(0,len(self.InputList)):
            self.afterEncodingFanoList[str(self.InputList[i])]=self.FanoList[i]

    def devid(self, start, end, List):
        """
        降序序列二分
        :param list:待分序列
        :return: 分割结点 i ，i之后划分为一组
        """
        sum = 0
        for i in range(start, end):
            sum += List[i]
        differ = []
        differSum = 0
        for i in range(start, end):
            differSum += List[i]
            differ.append(abs(2 * differSum - sum))
        return differ.index(min(differ))

    def code(self, start, breakpoint, end, input):
        """
        使某一区间加“1”
        :param start:
        :param end:
        :param input:
        :return:
        """
        for i in range(start, breakpoint):
            input[i] += "1"
        for i in range(breakpoint, end):
            input[i] += "0"

    def FanoEncoding(self, start, end, sourceList, encodingList):
        """
        菲诺编码
        :param sourceList:输入序列
        :return: 编码后序列
        """
        if (start == end - 2):
            encodingList[start] += '1'
            encodingList[end - 1] += '0'
        elif (start == end - 1):
            pass
        else:
            breakpoint = self.devid(start, end, sourceList) + 1 + start
            self.code(start, breakpoint, end, encodingList)
            self.FanoEncoding(start, breakpoint, sourceList, encodingList)
            self.FanoEncoding(breakpoint, end, sourceList, encodingList)


    # Haffman Encoding start
    def createHuffmanEncodingList(self):
        self.createHuffmanTree()
        self.getHuffmanCode()

    def createHuffmanTree(self):
        """
        生成哈夫曼树，
        :return: 哈夫曼树头节点
        """
        HuffmanList = []
        for i in self.InputList:
            node = HuffmanNode(value=i)
            HuffmanList.append(node)
        self.HuffmanNodeList = []
        while len(HuffmanList) != 1:
            HuffmanList.sort(key=lambda node: node.value)
            tempNode = HuffmanNode(value=HuffmanList[0].value + HuffmanList[1].value)
            tempNode.left = HuffmanList[0]
            HuffmanList[1].father = tempNode
            tempNode.right = HuffmanList[1]
            HuffmanList[0].father = tempNode
            if HuffmanList[0].left == None and HuffmanList[0].right == None:
                self.HuffmanNodeList.append(HuffmanList.pop(0))
            else:
                HuffmanList.pop(0)
            if HuffmanList[0].left == None and HuffmanList[0].right == None:
                self.HuffmanNodeList.append(HuffmanList.pop(0))
            else:
                HuffmanList.pop(0)
            HuffmanList.insert(0, tempNode)
        self.HuffmanHeadNode = HuffmanList[0]
        self.HuffmanHeadNode.father = None

    def getHuffmanCode(self):
        codes = {}
        for i in self.HuffmanNodeList:
            code = ''
            name = str(i.value)
            while i.father != None:
                if i.is_left_child():
                    code += '0'
                else:
                    code += '1'
                i = i.father
            codes[name] = code
        self.afterEncodingHuffmanList = codes

    def printHuffmanCode(self):
        for key in self.afterEncodingHuffmanList.keys():
            print(key, ':', self.afterEncodingHuffmanList[key])


    # ShannonEncoding start
    def createShannonlist(self):
        lengthList = []
        FList = []
        FRect = []
        p = 0
        for i in range(0, len(self.InputList)):
            lengthList.append(int(math.log(1 / self.InputList[i]) / math.log(2) + 1))
            p += self.InputList[i]
            FList.append(p)
            if i == 0:
                FRect.append(0.5 * self.InputList[i])
            else:
                FRect.append(FList[i - 1] + 0.5 * self.InputList[i])
        afterEncodingShannonList={}
        for i in range(0,len(lengthList)):
            afterEncodingShannonList[str(self.InputList[i])]=self.float2bin(FRect[i],lengthList[i])
        self.afterEncodingShannonList=afterEncodingShannonList

    def float2bin(self,number, length):
        first, dec = str(number).split('.')
        first = int(first)
        dec = int(dec)
        res = bin(first).lstrip("0b")
        i = 0
        while dec and i < length:
            if len(str((self.int2float(dec)) * 2).split('.'))==2:
                first, dec = str((self.int2float(dec)) * 2).split('.')
                dec = int(dec)
                res += first
                i += 1
            else:
                first = str((self.int2float(dec)) * 2).split('.')
                dec=0
                # print(first)
                res+=first[0]
                i+=1
        for _ in range(len(res), length):  # 补满 8 位
            res += "0"
        return res

    def int2float(self,num):
        while num > 1:
            num /= 10
        return num

class HuffmanNode():
    def __init__(self, name=None, value=None):
        self.name = name
        self.value = value
        self.left = None
        self.right = None
        self.father = None

    def is_left_child(self):
        return self.father.left == self

    def is_right_child(self):
        return self.father.right == self
